package leetcode_800;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 *@author 周杨
 *RandomPickWithBlacklist_710 实现随机从list选取一个没有的元素
 *describe:重排map AC 74%
 *2018年10月11日 上午11:02:08
 */
public class RandomPickWithBlacklist_710 {
	 	int M;
	    Random r;
	    Map<Integer, Integer> map;
	    public RandomPickWithBlacklist_710(int N, int[] blacklist) {
	        map = new HashMap<Integer, Integer>();
	        for (int b : blacklist) // O(B)
	            map.put(b, -1);
	        M = N - map.size();//剩下的部分remap找位置固定
	        for (int b : blacklist) { // O(B)
	            if (b < M) { // re-mapping
	                while (map.containsKey(N - 1))
	                    N--;//从底往上移动
	                map.put(b, N - 1);
	                N--;
	            }
	        }
	        r = new Random();
	    }
	    
	    public int pick() {
	        int p = r.nextInt(M);
	        if (map.containsKey(p))
	            return map.get(p);
	        return p;
	    }
}
